package com.atcumt.Carl;

import com.atcumt.Carl.LinkedList.ListNode;

public class Test {
    
    public ListNode combineTwoDisorderNodeToOrder (ListNode node1, ListNode node2) {
        // write code here
        if (node1 == null || node2 == null) {
            return node1 == null ? node2 : node1;
        }
        ListNode n1 = sortList(node1);
        ListNode n2 = sortList(node2);
        if (n1.val <= n2.val) {
            n1.next = combineTwoDisorderNodeToOrder(n1.next, n2);
            return n1;
        } else {
            n2.next = combineTwoDisorderNodeToOrder(n1, n2.next);
            return n2;
        }
    }
    private static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        ListNode dummyHead = new ListNode(-1);
        ListNode ans = dummyHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                dummyHead.next = left;
                left = left.next;
            } else {
                dummyHead.next = right;
                right = right.next;
            }
            dummyHead = dummyHead.next;
        }
        dummyHead.next = left != null ? left : right;
        return ans.next;
    }
}
